// 见Evernote！

class Solution {
public:
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    // int backPackIII(vector<int> &A, vector<int> &V, int m) {
    //     // write your code here
    //     vector<int> record(m + 1);
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         for (int j = m; j >= A[i]; --j)
    //         {
    //             int t = j;
    //             int tmp = 0;
    //             while (t >= A[i])
    //             {
    //                 t -= A[i];
    //                 tmp++;
    //                 record[j] = max(record[j], record[t] + V[i] * tmp);
    //             }
    //         }
    //     }
    //     return record[m];
    // }
    
    // backPackII从后往前就是为避免重复取，直接从前往后就行了
    int backPackIII(vector<int> &A, vector<int> &V, int m) {
        vector<int> record(m + 1);
        for (int i = 0; i < A.size(); ++i)
        {
            for (int j = 0; j <= m - A[i]; ++j)
            {
                record[j + A[i]] = max(record[j + A[i]], record[j] + V[i]);
            }
        }
        return record[m];
    }
};

class Solution {
public:
    /**
     * @param a: an integer array
     * @param v: an integer array
     * @param m: An integer
     * @return: an array
     */
    int backPackIII(vector<int> &a, vector<int> &v, int m) {
        int n = a.size();
        vector<vector<int>> rec(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                rec[i][j] = rec[i - 1][j];
                if (j >= a[i - 1]) {
                    rec[i][j] = max(rec[i][j], rec[i][j - a[i - 1]] + v[i - 1]);
                }
            }
        }
        return rec[n][m];
    }
};

class Solution {
public:
    /**
     * @param a: an integer array
     * @param v: an integer array
     * @param m: An integer
     * @return: an array
     */
    int backPackIII(vector<int> &a, vector<int> &v, int m) {
        vector<int> rec(m + 1, 0);
        for (int i = 0; i < a.size(); ++i) {
            for (int j = a[i]; j <= m; ++j) {
                rec[j] = max(rec[j], rec[j - a[i]] + v[i]);
            }
        }
        return rec.back();
    }
};